Advances in silicon technology increasingly allow larger and more complex designs to be formed on a single chip. Designs may consist of millions or tens of millions of transistors on a single chip. At the same time, however, market demands continue to push designers to develop designs more rapidly and efficiently. A recent trend to increase design speed and efficiency involves the re-use or recycling of electronic circuit blocks or subsystems, commonly referred to as “cores” or “IPs” (for “Intellectual Properties”), hereinafter referred to for convenience as “virtual component blocks” or “VCs.” Once the design for a virtual component block has been tested and verified, it can be re-used in other applications which may be completely distinct from the application which led to its original creation. For example, a subsystem for a cellular phone ASIC may contain a micro-controller as well as a digital signal processor and other components. After the design for the cellular phone subsystem has been tested and verified, it could be re-used (as a virtual component block) in, for example, an automotive application. Design reuse of virtual component blocks allows a designer to complete a design much faster than building the entire design from scratch, and avoids the need for debugging, testing and verification of the subsystems embodied in the virtual component block.
While virtual components have been found to be convenient for expediting and simplifying the circuit design process, the successful use of virtual component blocks hinges on the ability to accurately characterize their timing and functionality. A number of techniques have been developed or proposed for perform timing analyses on virtual component blocks, including static timing analysis and functional timing analysis.
Static timing analysis involves the calculation of a worst-case structural (or topological) delay between a circuit's input and an output, but ignores the functionality of the circuit. Static timing analysis methods make no attempt to detect false paths, which are signal paths never sensitized (activated) in actual operation. The use of functional information to improve the accuracy of static timing analysis methods has been proposed in the past—for example, in P. McGeer et al, Integrating Functional and Temporal Domains in Logic Design: The False Path Problem and Its Implications, Kluwer Academic Publishers (Hingham, Mass. 1991).
Functional timing analysis methods attempt to rely on the fact that the delays in a circuit are linked to the way a circuit functions. “Functionality” in this context refers to the logical value computed for each circuit node, given an input vector. Unlike traditional static timing analysis, functional timing analysis uses a circuit's function as well as its structure to characterize delays and timing constraints.
Two widely used methods for functional timing analysis are symbolic analysis via binary-decision diagrams (BDDs), and boolean search methodologies that systematically enumerate the input space. Both methods assume that the delays of a circuit depend on the values of all of its inputs. These methods aim at finding an input vector that sensitizes the true longest path. However, they both have the disadvantage that their complexity increases exponentially with circuit size, limiting their applicability, or requiring unacceptably large amounts of computation resources for larger circuit designs.
A more practical approach is to assume that a circuit's delays depend on only a subset of its inputs. This is typical of datapath circuits, where a small number of control inputs determine the delays between a large number of data inputs and data outputs. A simple example is shown by a circuit 50 in FIG. 1, wherein the control inputs 60 to a large extent determine the delays between the data inputs 55 and the data outputs 70.
Methods of timing analysis have been developed based upon the recognition that the control inputs play a role in determining the delays between the data inputs and outputs. These methods generally trade accuracy for computation efficiency. For example, some static timing analyzers employ a systematic case analysis capability whereby the user sets some inputs to constant values prior to performing the timing analysis. A drawback with such timing analysis methods is that they suffer from delay underestimation. Delay underestimation is a serious problem in circuit design because it can lead to incorrect operation.
One timing analysis benchmark involves calculation of the delay in a so-called “floating mode” of operation. In a floating mode of operation, each circuit node initially has an unknown value. Upon the application of an input vector to the circuit, the circuit node undergoes a series of transitions or events before it eventually stabilizes at a value determined by the circuit's internal static functionality.
Examples of event propagation using principles of “controlling” and “non-controlling” values are illustrated in FIGS. 2A and 2B, for the simple case of a two-input AND gate. A controlling value (CV) at a gate input is one that determines the output of the gate regardless of the values of the other inputs. A non-controlling value (NCV) does not change the gate output by itself. For an AND gate, the controlling and non-controlling values are 0 and 1, respectively. The arrival time of a gate output is determined by the earliest input with a controlling value, if it exists; otherwise, the latest input with the non-controlling value determines the output arrival time. In FIG. 2A, input “a” is a controlling value because it will eventually become 0, whereas in FIG. 2B, neither input “a” nor “b” is a controlling value because both will stay at 1. Because, input “a” has a controlling value in FIG. 2A, the gate output arrival time “Tz” is determined only by the arrival time Ta of input “a”, plus the gate delay d. In FIG. 2B, however, because neither input “a” nor “b” has a controlling value, the output arrival time Tz is given by the latest input arrival time (in this example, Tb) plus the gate delay d. Because the last arriving event at any node determines the delay up to that node, the terms “arrival time” and “delay” are used interchangeably herein.
For a generic gate having inputs “a” and “b” and output “z” in floating mode (FM), these concepts may be shown in the form of a truth table, TzFM, such as appearing in Table 1 below.
TABLE 1VaVbTZFMCVCVmin(Ta'Tb) + dCVNCVTa + dNCVCVTb + dNCVNCVmax(Ta'Tb) + d
It is possible to write a logical expression (or predicate) that describes whether an input event propagates from a gate input to the gate output; such expressions are sometimes referred to as “sensitization conditions.” Referring back to FIGS. 2A and 2B, the sensitization condition for the path from input “b” to gate output “z” may be denoted CONDbz. In FIG. 2A, this path is “sensitized” so that CONDbz is 1 (true). In FIG. 2B, this path is not “sensitized” so that CONDbz is 0 (false). A number of sensitization conditions have been proposed. Two such sensitization conditions, referred to as “viability” and “floating-mode condition,” have been used in calculating the floating-mode arrival time of Table 1. The values of TzFM shown in Table 1 are the least pessimistic that can be achieved in “floating mode.” Thus, for any conditional expression TzX to be correct for delay calculation using the conventional “floating mode” conditional analysis, it must exceed the delay values expressed in Table 1 above; that is, it must satisfy the relationship:Txz≧TzFM∀νa′∀νb
Several other sensitization conditions have been proposed. “Static sensitization” is a commonly used sensitization condition which has arisen from test generation. Static sensitization is based on the premise that a path is “sensitized” only if all its side inputs (i.e., inputs of a gate that are not on the delay path) have non-controlling values. A computational advantage of this condition is that it depends only on the final (stable) values of the inputs and is independent of the input event times. However, a drawback of static sensitization techniques is that, if the two inputs of a gate are controlling, they incorrectly assume that the paths from both inputs are false.
In contrast to static sensitization, the simplest (but most pessimistic) path sensitization condition is that of topological analysis where events always propagate. Thus, for the two-input gate case, the output arrival time, which may be designated TzTOP, is always the maximum of the input event times plus the gate delay. Table 2 below summarizes and compares the arrival times for floating mode, static sensitization, and topological analysis.
TABLE 2VaVbTzFMTzSTTzTOPCVCVmin(Ta'Tb) + d−∞max(Ta'Tb) + dCVNCVTa + dTa + dmax(Ta'Tb) + dNCVCVTb + dTb + dmax(Ta'Tb) + dNCVNCVmax(Ta'Tb) + dmax(Ta'Tb) + dmax(Ta'Tb) + d
In Table 2, the term “−∞” indicates that no event propagates; hence, an effectively “infinite” delay. As may be observed from viewing Table 2, the output arrival time TzTOP under a topological analysis where events always propagate is always greater than or equal to the output arrival time TzFM using floating mode conditional analysis. Topological analysis is commonly used in static timing analysis tools. A big disadvantage is its failure to detect any false paths, leading to overly pessimistic results.
A need exists for a functional timing analysis of circuit blocks that has improved accuracy, yet is not computationally burdensome.